// zynga.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"

#include <map>

//http://www.careercup.com/page?pid=zynga-interview-questions


//We have array that contain integer number, I would like to find the numbers that repeated k time in this array. 
//The array is not sorted, and the numbers are not bounded. 
//Example, 
//A(20, 6, 99, 3, 6, 2, 1,11,41, 31, 99, 6, 7, 8, 99, 10, 99, ,6) 
//Find the numbers repeated more than 3 times. 
//Answer: 6,99 
//possible answer using bit wise operations (xor) or combination? Efficiency in running time Big(o) is required as well as the space capacity.

void find_k_times(int a[], size_t n, int k, int (&r)[100])
{
	std::map<int, int> buffer;

	int j = 0;
	for(size_t i = 0; i < n; ++i)
	{
		buffer[a[i]]++;

		if( buffer[a[i]] == k )
			r[j++] = a[i];
	}
}




//Given that a disk page can hold at most 1K bytes, a search key uses 4 bytes, and a pointer uses 4 bytes. 
//Can we analyze the size of an expendable hashing index to index a table column which is defined using unique constraint. 
//What would be the minimum and maximum size of the expendable hasting index if the bucket address table is fully extended?


//find least common ancestor in btree. 
//Note:its btree not bst


//find all broken links in a web page


//how to implement LRU for ecommerce site --> use linklist+map


//How will you store friend-to-friend relation of facebook in db


//Find duplicates in Array. I presented solution in O(n) time and space using hash. Finally did it in O(n) time and constant space. 
//Assumption: range of numbers is known.

//Reverse a Linked List. Iterative and then recursive.


//Reverse words : "I love to play" becomes "play to love I". 
//He wanted it to be done in place.

//n=4 and k=3 . team name can be formed by four digits 1,2,3,4 . so n=4 now make team number using any three digits so that b1<b2<b3. 
//Basically print numbers which are in form b1<b2<b3..e.g. 123,124,234 etc

//write a function that takes two numbers a and b and returns a.b eg: a=10 and b=12 output will be 10.12

int _tmain(int argc, _TCHAR* argv[])
{
	{
		int a[] = {20, 6, 99, 3, 6, 2, 1,11,41, 31, 99, 6, 7, 8, 99, 10, 99,6};

		int r[100] = {0};
		find_k_times(a, sizeof(a)/sizeof(int), 3, r);

		int t = 3;
	}

	return 0;
}

